#ifndef UNION_FIND_SET_H
#define UNION_FIND_SET_H

#include <iostream>
#include <string>
#include <vector>
#include <ctime>

using namespace std;

typedef struct node
{
    int index;
    int rank;
    node* p;
} node;

class Union_Find_Set
{
private:
    int num_node;
    vector<node> forest;
    vector<vector<int>> G;

    void Link(node *x, node *y);
    void Union(node *x, node *y);
    node* Find_Set(node *x);
    void Make_Set(node *x);
    void Connected_Components();
    bool Same_Component(node* u, node* v);
    int get_union_num();

public:
    Union_Find_Set(vector<vector<int>> mat);
    void run();
};

#endif